The Angel Problem [Game Theory]

Shall we play a game? You're an Angel on an infinite grid. Each turn, you can jump up to K spaces away. Let's say K is 10 for this example, meaning that you can jump to anywhere within this boundary. But your arch-nemesis The Devil, is watching. On The Devil's turn, he can remove one square anywhere on the infinite grid. And the angel can no longer land there. So the question is: Can the devil eventually trap the angel, or does the angel have a strategy to avoid capture forever?

This is a fascinating game theory problem posed by none other than John Conway himself. What makes it so difficult is that it's played over infinite time and space. At first, your intuition is probably telling you: Of course, the angel can win! I mean, she's so maneuverable. And the devil can only block one square at a time? How can the devil ever have enough time to trap the angel? But today, I'll be the devil's advocate. Muhahaha!

The Angel's Movements: A Game Theory Perspective

Let's look at the Angel's movements a little closer with a game theory perspective. One thing to notice is that the angel would never want to move to a space that she could have landed on previously. But the proof is simple. If she took more than one turn to get to a spot that she could have reached before, then the result would be exactly the same but the devil got extra moves in between. So it's impossible for this strategy to ever help The Angel. It strictly benefits The Devil. That means all these spaces are effectively gone. In fact, it can be treated the same as if The Devil himself blocked all of those squares. So even though The Devil only blocks one square each turn, The Angel blocks 100.

But that's no problem. We can just keep moving away, right? Let's suppose we restrict our movement to always be some amount north. Well, The Devil has a plan for us. I'm going to switch to K = 1 to make the visuals easier. But far away, The Devil can start building a wall above our cone of movement, leaving big gaps. Once The Angel gets halfway there, the problem recurses as he fills in the next squares. The Devil has half the time, but also half the distance so he can do it. This keeps repeating until the wall is entirely dense, and The Angel can't move north anymore. This works with any K. But the required distance away to build the wall increases super exponentially.

Okay. Well, maybe saying we had to move north was too restrictive. I mean, we have way more maneuverability after all, right? Well, Conway also showed that an angel that strictly increases her distance from the origin can also be trapped using a very similar argument. The Devil can pretend the angel has a K four times larger and use alternating turns to build walls on all four sides. So have I convinced you? Is there any hope for the angel? Are you willing to sell your soul to the devil? Muhahahaha!

Hope for the Angel: A Surprising Revelation

Well, this was an open problem in mathematics and it was only recently proven in 2006. Turns out that the angel can win! Surprisingly, with a K as low as 2. The proof is pretty complicated, but it uses some kind of maze-solving argument. I guess you could say The Devil is in the details. Anyway, I've only ever seen this problem as a purely mathematical one. So I thought it'd be really cool to make it into a real game that you can actually play with an AI. But unfortunately, due to the ENORMOUS distances involved, it would take an eternity to play and just be super boring. Nonetheless, I hope you found this topic as interesting as I did. Thanks for watching!

Conclusion

In the game of the Angel and the Devil on an infinite grid, it may seem like the Devil has the upper hand. With the ability to block one square each turn, it seems impossible for the Angel to avoid capture forever. However, through a game theory perspective, it becomes clear that the Angel can strategically maneuver to prevent the Devil from trapping her. While the Devil can build walls and fill in squares, the Angel can always find a way to increase her distance from the origin and avoid being trapped. It's a game of wit and strategy, and in the end, the Angel can emerge victorious. So, don't sell your soul to the Devil just yet. The Angel has a plan. Muhahaha!